package a09_贪心算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * a20_合并区间复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/5/6
 */
public class a20_合并区间复习2 {

    //[[1,3],[2,6],[8,10],[15,18]]
    public static void main(String[] args) {
        int[][] merge = merge(new int[][]{{2,3}, {4,5}, {6,7}, {8,9},{1,10}});
        for (int[] ints : merge) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (interval1,interval2) -> {
            if(interval1[0] == interval2[0]){
                return interval1[1] - interval2[1];
            }else {
                return interval1[0] - interval2[0];
            }
        });

        LinkedList<int[]> list = new LinkedList<>();
        list.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] <= intervals[i-1][1]){
                int[] ints = list.removeLast();
                ints[1] = Math.max(ints[1], intervals[i][1]);
                intervals[i][1] = ints[1];
                list.add(ints);
            }else {
                list.add(intervals[i]);
            }
        }


        return list.stream().toArray(int[][]::new);
    }
}
